%!TEX program = xelatex
%!TEX TS-program = xelatex
\documentclass{lonac}
\usepackage{wrapfig}
\punctstyle{kaiming}
\begin{document}
\thispagestyle{empty}
\begin{center}
\Huge{\vspace*{6.5em}\heiti{Lon.AC NOI大纲知识点拆解学习}
\par\vspace*{1em}
\fangsong{入门级}
\par\vspace*{8em}
\LARGE{\kaishu{2024年2月\par 海南·海口}}
}
\end{center}
\normalsize
\newpage
\thispagestyle{empty}
\tableofcontents
\newpage
\addtocounter{page}{-2}
\section{预备知识}
\begin{intro}
\kaishu{\indent「合抱之木，生于毫末；九层之台，起于累土；千里之行，始于足下。」\par\hfill ——老子《道德经》\par}\vspace*{1.5em}
\fangsong{
CSP竞赛是每年众多信息学竞赛中比较基础的比赛。在CSP竞赛中获得一定的成绩也是以后参加NOIP乃至更高级比赛的重要条件。

2023年，CCF发布了最新版《NOI竞赛大纲》。按照大纲要求，入门组比赛会考察《NOI竞赛大纲》中难度等级为$1\sim 5$级的知识点。接下来，我们将力求全面地对入门组比赛所考察到的所有知识点做一个介绍，并在每章后配有相关习题，所有习题均选自近几年来 CSP入门组竞赛以及NOIP竞赛原题或较高质量的模拟题，并有详细的答案解析和C++示例代码以供参考。

CSP入门级竞赛（以下简称CSP-J）分为两轮，其中第一轮是两个小时的笔试，主要考察基础知识；第二轮是上机测试，主要考察编程能力，只有在通过第一轮之后才有资格参加第二轮竞赛。“预备知识”这一章节要介绍的主要是一些最为基础的知识点，这些知识点主要在第一轮中考察，虽然本章的内容似乎极少涉及到真正的编程和算法，但是有着扎实的理论基础是我们顺利通过第一轮竞赛的保障也是我们进一步学习更多知识的必要条件。}
\end{intro}
\subsection{基础知识和编程环境}
\begin{point}
\begin{itemize}
\item 计算机的基本构成（CPU、内存、I/O 设备等）\dotfill〔1〕\footnote{指对应2023最新版NOI大纲的知识点，“〔〕”里的数字指NOI大纲内标注的“难度系数”，一般来讲数字越大难度越高}
\item 计算机的历史和常见用途\dotfill〔1〕
\item 位、字节与字\dotfill〔1〕
\end{itemize}\end{point}

\subsubsection{计算机的历史和常见用途}
1946年，第一台通用计算机ENIAC在美国诞生，它的占地面积约170平方米，包含了17,468根电子管，计算速度是每秒5000次加法或400次乘法，这个数字虽然在现在的电子计算机面前不值一提，但仍是手工计算的20万倍。

几十年以来，计算机的发展日新月异，从电子管、晶体管计算机到现在集成电路以及超大规模集成电路计算机，计算机的运算速度不断提升，但计算机的工作原理变化不大。早在1945年，冯·诺伊曼就提出了一直沿用至今的“存储程序”工作原理。其实，科学计算的尝试还可以追溯到更早，1936年，英国人艾伦·麦席森·图灵便提出了“图灵机”这个计算模型\textbf{（注意：图灵机不是真正的计算机，只是理论模型）}

如今，计算机一渗透到人们生活和工作的各个层面中，主要体现在以下几个方面的运用：
\begin{enumerate}
\item \textbf{科学计算}\par
科学计算（或数值计算）是指利用计算机来完成科学研究和工程技术中提出的数学问题的计算。在现代科学计算技术工作中，科学计算问题是大量的和复杂的。利用计算机的高速计算、大存储容量和连续计算的能力，可以实现人工无法解决的各种科学计算问题。
\item \textbf{信息处理}\par
信息处理（数据处理）是指对各种数据进行收集、存储、整理、分类、统计、加工、利用、传播等一系列活动的统称。
\item \textbf{自动控制}\par
自动控制（过程控制）是利用计算机及时采集检测数据，按最优值迅速地对控制对象进行自动调节或自动控制。采用计算机进行自动控制，不仅仅可以大大提高控制的自动化水平，而且可以提高控制的及时性和准确性，提高产品质量及合格率。目前，计算机过程控制已在机械、冶金、石油、化工、纺织、水电、航天等部门得到了广泛的应用。
\item \textbf{计算机辅助技术}\par
计算机辅助技术是指利用计算机帮助人们进行各种设计、处理等过程，它包括计算机辅助设计（CAD）、计算机辅助制造（CAM）、计算机辅助教学（CAI）和计算机辅助测试（CAT）等。另外计算机辅助技术还有辅助生产、辅助绘图和辅助排版等。
\item \textbf{人工智能}\par
人工智能(Artificial Intelligence,AI)又可称为智能模拟，是计算机模拟人类的智能活动，诸如感知、判断、理解、学习、问题求解和图像识别等。人工智能的研究目标是使计算机更好的模拟人的思维活动，那是的计算机将可以完成更复杂的控制任务。
\item \textbf{网络应用}\par
随着社会信息化的发展，通信业也发展迅速，计算机在通信领域的作用越来越大，特别是促进了计算网络的迅速发展。目前，全球最大的网络(Internet,国际互联网)已把全球的大多数计算机联系在一起。除此以外，计算机在信息高速公路、电子商务、娱乐和游戏等领域也得到了快速的发展。
\end{enumerate}
\subsubsection{计算机的基本构成}

根据冯·诺伊曼体系结构，计算机系统由\CJKunderdot{运算器}、\CJKunderdot{控制器}、\CJKunderdot{存储器}、\CJKunderdot{输入设备}和\CJKunderdot{输出设备}五个部分组成。这五个部分的工作流程如图所示：\par
\begin{center}
\includegraphics[width=8cm]{./pic/1.1-1.pdf}
\end{center}

CPU由运算器、控制器、存储器三部分组成。运算器又称算术逻辑单元（Arithmetical Logic Unit,ALU），主要功能是完成对数据的算术运算、逻辑运算和逻辑判断等操作。 控制器（Control Unit,CU）。是整个计算机的指挥中心，根据事先给定的命令发出各种控制信号，指挥计算机各部分的工作。 寄存器（Register）：主要用来存储存放指令、数据和位址。 这三个部件通过CPU总线进行数据和指令的传递。


其中，存储器分为内存储器（简称内存）和外存储器（简称外存）。内存储器速度较快，而外存储器相对速度较慢。内存储器的数据存取速度虽然很快，但与CPU相比还存在一定的差距，为了加快数据存取速度，CPU内部又增加了高速缓冲存储器（Cache）。于是Cache、内存储器和外存储器共同构成了计算机的三层存储层次结构。CPU只能直接访问储存在内存中的数据，而外存中的数据只有先调入内存后才能被中央处理器访问、处理。

\subsubsection{计算机处理数据的单位}
内存储器由许多存储单元组成，每个单元能存放一个二进制数或一条由二进制编码表示的指令。这一个单元称之为一个\CJKunderdot{二进制位}（Bit）。一个二进制位只有0、1两种状态。

CPU在处理指令时不能一次读取全部的数据，不同计算机能够同时处理的数据量也不同，一次性处理事务的固定长度称为“\CJKunderdot{字}”，其大小称为“\CJKunderdot{字长}”，内存储器中的所有存储单元都有一个唯一的“地址”，CPU根据地址获取内存中的数据，字长就决定了CPU的寻址空间和机器指令中二进制代码的位数。例如：在32位计算机中，CPU一次能与内存交流的数据量就为32个二进制位（4个字节），现在流行的计算机处理器绝大多数已达到64位字长。

更大的存储单位如下表所示\footnote{表中的KB、MB等严格来讲应为“KiB”、“MiB”，但根据近几年CSP第一轮真题来看，没有出现KiB、MiB等表述，反倒用KB、MB等来代替，因此至少在OI比赛中可以大致认为这两种写法是等价的}，其中，每相邻两个存储单位之间相差$2^{10}=1024$倍。

\begin{figure}[h]
\centering
\includegraphics[width=8cm]{./pic/1.1-2.pdf}
\end{figure}

\begin{problem}{例题}
\begin{enumerate}
\item \songti{32位计算机和64位计算机的区别是}\hfill（\qquad）
\xx{最大支持的硬盘大小不同}{寻址空间不同}{显示分辨率不同}{内存大小不同}
\item \fangsong{【2020·入门级第一轮】}\songti{在内存储器中每个存储单元都被赋予一个唯一的序号，称为}\hfill（\qquad）
\xx{地址}{序号}{下标}{编号}
\item 现有一段 $24$ 分钟的视频，它的帧率是 $30$ Hz，分辨率是 $1920\times 1080$， 每帧图像都是 $32$ 位真彩色图像，使用的视频编码算法达到了 $25\%$ 的压缩率。则这个视频文件占用的存储空间大小约是\hfill（\qquad）
\xx{668 GiB}{334 GiB}{85 GiB}{500 GiB}
\end{enumerate}
\end{problem}

\begin{solution}
\begin{enumerate}
\item B，地址总线数量不同，寻址空间不同。
\item A
\item C，$\frac{24\times 60 \times 30 \times 1920 \times 1080 \times 32}{8\times 1024 \times 1024 \times 1024} \times 0.25 = 83.4274$
\end{enumerate}
\end{solution}

\subsubsection{原码、补码、反码}

计算机在处理数据时采用二进制编码，我们称这些二进制数为机器数，机器数是有符号的，例如：10000001代表$-1$。在计算机中用机器数的最高位存放符号位，0表示正数，1表示负数。

因为机器数带有符号位，所以机器数的形式值不等于其真实表示的值，机器数1000 0001为例，二进制真值（首位为符号位）为$-1$，而形式值（首位代表1的值）为129；因此将带符号的机器数的真正表示的值称为机器数的真值。

对于正数而言，原码、反码、补码都是一样的，都等于其二进制真值。但是对于负数而言，原码，反码，补码表示各有不同。

对于负数，原码仍是其二进制真值（符号位是1），反码的值是其原码除了符号位以外按位取反（例如：8位机器数10000001的补码是：11111110），而补码是其反码的值$+1$，例如：8位机器数10000001的补码是：11111111。

以上都是对于整数的表示，对于浮点数的表示类似于我们十进制中的“科学记数法”。例如：在“科学记数法”中，十进制小数“1000.0234”可表示为：$1.0000234\times 10^3$，计算机中先把浮点数转换成一个小于2的正数（称为“尾数”），再添加一个“指数”表示将一个2的幂次乘到尾数后面得到原浮点数。

\begin{problem}{例题}
\begin{enumerate}
\item \songti{以补码存储的 8 位有符号整数 10110111 的十进制表示为}\hfill（\qquad）
\xx{-73}{183}{72}{-72}
\end{enumerate}
\end{problem}

\begin{solution}
\begin{enumerate}
\item B
\end{enumerate}
\end{solution}
\subsubsection{进制转换}
计算机内部使用的是二进制，所有的数值数据和非数值数据，都是由“0”和“1”这两个数字符号加以组合而成的。计算机只用二进制的两个数码“0”和“1”来实现算数和逻辑运算，而人们仍然用十进制的形式向计算机中输入原始数据，并让计算机也用十进制形式显示和打印运算结果。所以，必须有一种自动转换方法，即让数据输入计算机后，将十进制转换成对应的二进制数，并在处理完毕后，再自动将二进制结果转换位十进制数。 为了表达方便起见，常在数字后加一缩写字母后缀作为不同进制的标识。各种进制数的后缀字母分别为： 
\begin{center}
B:二进制数 \ \ \   O：八进制数 \par
D:十进制数 \ \ \   H:十六进制数 
\end{center}
对于十进制数，通常不加后缀，也即十进制数后的字母D可省略。
\newpage
\section{C++程序设计}
\begin{intro}
\kaishu{\indent 子曰：「工欲善其事，必先利其器。」\par\hfill ——《论语·卫灵公》\par}\vspace*{1.5em}
\fangsong{程序是算法与数据结构的载体，是解决 OI 问题的工具，在 OI 中，最常用的编程语言是 C++。虽然学习OI不仅仅局限于学习计算机语言，但毫无疑问，学习编程是学习 OI 最基础的部分，扎实的C++基础也是我们以后解决OI问题不可或缺的“利器”。}
\end{intro}
\subsection{输入与输出}
\subsubsection{第一个C++程序}

\begin{wrapfigure}{r}{0.3\textwidth}
\centering
\scriptsize
\begin{colorbox2}{瀑布蓝}
\textcolor{瀑布蓝}{\heiti{什么是 \texttt{\#include}}？}

\kaishu
\texttt{\#include} 其实是一个预处理命令，意思为将一个文件「放」在这条语句处，被「放」的文件被称为头文件。也就是说，在编译时，编译器会「复制」头文件 \texttt{iostream} 中的内容，「粘贴」到 \texttt{\#include <iostream>} 这条语句处。这样，你就可以使用 \texttt{iostream} 中提供的 \texttt{std::cin}、\texttt{std::cout}、\texttt{std::endl} 等对象了。

一般来说，应当根据你程序的需要来确定头文件。但如果你 \texttt{\#include} 了多余的头文件，只会增加编译时间，几乎不会对运行时间造成影响。目前我们只接触到了 \texttt{iostream} 和 \texttt{cstdio} 两个头文件，如果你只需要 \texttt{scanf} 和 \texttt{printf}，就可以不用 \texttt{\#include <iostream>}。

\end{colorbox2}
\vspace*{1.2em}
\begin{colorbox2}{瀑布蓝}
\textcolor{瀑布蓝}{\heiti{什么是 \texttt{main}} 函数？}
\kaishu

可以理解为程序运行时就会执行 \texttt{main()} 中的代码。

实际上，\texttt{main} 函数是由系统或外部程序调用的。如，你在命令行中调用了你的程序，也就是调用了你程序中的 \texttt{main} 函数（在此之前先完成了全局变量的构造）。

最后的 \texttt{return 0;} 表示程序运行成功。默认情况下，程序结束时返回 0 表示一切正常，否则返回值表示错误代码。这个值返回给谁呢？其实就是调用你写的程序的系统或外部程序，它会在你的程序结束时接收到这个返回值。如果不写 \texttt{return} 语句的话，程序正常结束默认返回值也是 0。

在 C 或 C++ 中，程序的返回值不为 0 会导致运行时错误（Runtime Error，RE）。
\end{colorbox2}
\end{wrapfigure}
如果你不想深究背后的原理，初学时可以直接将这个「框架」背下来：
\begin{lstlisting}[language=cpp]
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
    // do something...
    return 0;
}
\end{lstlisting}

在写好以上框架后，在\code{main}函数内写上：
\begin{lstlisting}[language=cpp]
int x, y, z;                               // 声明变量
cin >> x >> y;                             // 读入 x 和 y
z = x + y;                                 // 计算 x + y
cout << z << endl;                         // 输出，并换行
\end{lstlisting}

\texttt{注意：请在编写前注意开启英文输入法。}



\begin{tips}
在 C++ 代码中，注释有两种写法：
\begin{enumerate}
\item \textbf{行内注释}\par
以 \texttt{//} 开头，行内位于其后的内容全部为注释。
\item \textbf{注释块}\par
以 \texttt{/*} 开头，\texttt{*/} 结尾，中间的内容全部为注释，可以跨行。
\end{enumerate}
注释对程序运行没有影响，可以用来解释程序的意思，还可以在让某段代码不执行（但是依然保留在源文件里）。

在工程开发中，注释可以便于日后维护、他人阅读。

在 OI 中，很少有人写许多注释，但注释可以便于在写代码的时候理清思路，或者便于日后复习。而且，如果要写题解、教程的话，适量的注释可以便于读者阅读，理解代码的意图。
\end{tips}

\begin{problem}{例1}
不要复制代码，尝试自行实现A+B Problem
\end{problem}

\begin{problem}{例2}
尝试同时输出 $x+y,x-y,x\times y,x \div y$。
\end{problem}

\begin{tips}
C++中用\texttt{a * b}计算$a\times b$，用\texttt{a / b}计算$a\div b$
\end{tips}

\begin{tips}
思考下为什么输入“\texttt{3 2}”时，输出$x \div y$的值不是小数？应该如何改进？
\end{tips}

\begin{problem}{例3}
把例1中 \code{using namespace std;}一句去掉，看看结果有没有变化，再把\texttt{cin、cout、endl}替换成\texttt{std::cin、std::cout、std::endl}试试。
\end{problem}

\begin{tips}
C++ 标准库的所有内容均定义在 \texttt{std} 命名空间中，如果你定义了一个叫 \texttt{cin} 的变量，则可以通过 \texttt{cin} 来访问你定义的 \texttt{cin} 变量，通过 \texttt{std::cin} 访问标准库的 \texttt{cin} 对象，而不用担心产生冲突。

如果执行了 \texttt{using namespace std;}，就会将 \texttt{std} 中的所有名字引入到全局命名空间当中。这样，我们就可以用 \texttt{cin} 代替 \texttt{std::cin}，用 \texttt{cout} 代替 \texttt{std::cout}。
\end{tips}

\end{document}